00100	.DEVICE XGP
00200	
00300	.FONT 1 "FIX25"
00400	.FONT 2 "SIGN57"
00500	.FONT 3 "SHD40"
00600	.FONT 4  "BDI25"
00700	.FONT 5  "NGR20"
00800	.TURN ON "↓_π{"
00900	.TURN ON "⊗" FOR "%"
01000	.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
01100	.MACRO E ⊂ APART END ⊃
01200	.TABBREAK
01300	.COMPACT
01400	.SELECT 1
     

00100	.PORTION TITLEPAGE
00200	.EVERY FOOTING(,⊗5{DATE}⊗*,)
00300	.BEGIN CENTER 
00400	.RETAIN
00500	.PAGE FRAME 54 HIGH 91 WIDE
00600	.EVENLEFTBORDER←ODDLEFTBORDER←1000;
00700	.FONT 6 "SGN114"
00800	⊗6   BEINGS:⊗*
00900	
01000	⊗2REPRESENTATION OF KNOWLEDGE
01100	AS INTERACTING MODULES
01200	⊗*
01300	
01400	⊗4Applied to Automatic Program Synthesis⊗*
01500	.END
01600	.GROUP SKIP 10
01700	Fourth Draft:  NOT FOR DISTRIBUTION
01800	.GROUP SKIP 10
01900	⊗3DOUG LENAT 
02000	
02100	STANFORD UNIVERSITY
02200	
02300	ARTIFICIAL INTELLIGENCE LABORATORY⊗*
02400	
02500	.PORTION CONTENTS
02600	.GROUP SKIP 10
02700	⊗2TABLE OF CONTENTS⊗*
02800	.GROUP SKIP 10
02900	.SELECT 1
03000	.B
03100	    1.	Abstract  . . . . . . . . . . . . . . . .  1
03200	    2.	Introduction  . . . . . . . . . . . . . .  2
03300	    3.	Theory:   Ideas . . . . . . . . . . . . .  3
03400	    4.	Reality:  Examples  . . . . . . . . . . . 10
03500	    5.	Theory:   Design. . . . . . . . . . . . . 15
03600	    6.	Reality:  Examples  . . . . . . . . . . . 19
03700	    7.	Reality:  Results . . . . . . . . . . . . 23
03800	    8.	Theory:   Conclusions . . . . . . . . . . 28
03900	    9.	Acknowledgements  . . . . . . . . . . . . 32
04000		Appendix 1: BEING parts . . . . . . . . . A1.1
04100		Appendix 2: the BEINGs  . . . . . . . . . A2.1
04200		Appendix 3: BEING usage . . . . . . . . . A3.1
04300		Appendix 4: CF  program . . . . . . . . . A4.1
04400		Appendix 5: the dialogue creating CF  . . A5.1
04500		Appendix 6: trial running of CF . . . . . A6.1
04600		Bibliography  . . . . . . . . . . . . . . BIB.1
04700	.E
04800	.SELECT 1
     

00100	.PORTION ABSTRACT
00200	.PAGE FRAME 54 HIGH 74 WIDE
00300	.EVERY HEADING(⊗3BEINGS⊗*,,⊗4Doug Lenat⊗*)
00400	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {IF PAGE = 1 THEN 1 ELSE PAGE})
00500	.COUNT PAGE PRINTING "1"
00600	.NEXT PAGE
00700	.GROUP SKIP 10
00800	
00900	⊗21. ABSTRACT⊗*
01000	.GROUP SKIP 10
01100	
01200	Knowledge may be organized as  a  community  of  interacting  modules
01300	(e.g.,  ACTORS [Hewitt]), in which control also resides.  By granting
01400	each module a complex structure, yet constraining that that structure
01500	be   standard   over  all  the  modules,  some  new  theoretical  and
01600	experimental results were found.  The domain  of  this  research  was
01700	heuristic  automatic  synthesis of inductive inference LISP programs.
01800	Since these modules, called BEINGs, are the only  entities  permitted
01900	to  exist  theoretically, the generated code must also be a community
02000	of BEINGs.  Like the original pool, the newly synthesized BEINGS which
02100	comprise the target program can answer
02200	questions  about  themselves as they run.  An experimental system was
02300	partially implemented.  It  synthesized  a  few  programs  from  very
02400	restricted dialogues.  Some unexpected problems were encountered, and
02500	some aspects which were considered ignorable seem  not  to  be.   The
02600	performance  of  the  system  is discussed, and a preliminary view of
02700	BEINGs assessed.
     

00100	.PORTION THESIS
00200	⊗22. INTRODUCTION⊗*
00300	
00400		This  paper  reports  on a scheme for representing knowledge,
00500	partially  realized  in  an  experimental  system  (PUP6)  aimed   at
00600	generating  LISP  programs  from dialogues with the user. The methods
00700	employed are not formal, but rather involve structuring of  knowledge
00800	about  programming,  about  the  task  domain,  and about transfer of
00900	control.  To date, PUP6 has synthesized three significantly different
01000	target programs:  a concept formation program (similar to [Winston]),
01100	a grammatical inference program, and a simple information storage and
01200	retrieval on keys system  
01300	(referred  to  as, respectively, CF, GI, and INF).
01400	Specification is via rigid,
01500	extended dialogues carried on with the user,  in
01600	a  small  subset  of  English,  in  which  the task is delineated and
01700	questionable details are discussed.  The  specification  is  partial,
01800	and  the system makes assumptions continually. This is what is meant,
01900	in the sequel, by ⊗4Automatic Programming.  Target program⊗* will refer
02000	to code which has been successfully generated by such a system.
02100	This will typically be written in the same language as the system itself.
02200	⊗4Dialogue⊗* is the interactive communication between the user and the
02300	automatic programming system, which results in target code synthesis.
02400		The  CF  target  program  was cleanly specified, an annotated
02500	protocol was done, and the BEINGs needed to reproduce  the  reasoning
02600	present  in  that protocol were fasioned. Additions were made to PUP6
02700	before it could synthesize GI or INF.
02800		The  main  successes  of the experiment were that the desired
02900	reasoning steps in the original protocol
03000	were actually simulated, most of the BEINGs were used
03100	in  writing  more  than one of the programs, and the synthesized code
03200	could be interrupted and asked a few kinds of  questions.   The  main
03300	defects  were  the  inflexibility of the system to new dialogues, the
03400	inability for  the  user  to  add  new,  high-level,  domain-specific
03500	knowledge,  and  the verbosity of the system.  Some of these problems
03600	may arise from the annotated protocol technique employed to  get  the
03700	BEINGs  initially,  and  not  from  anything  inherent  to the BEINGs
03800	representation.
03900		Our  treatment will follow these lines:  First, the ideas are
04000	presented, including a  discussion  of  BEINGs.   Examples  are  then
04100	provided to illustrate these concepts. The next section describes the
04200	implementation, and explains the choice of targets.  Only  then  will
04300	performance  be  evaluated.  From  the experience with PUP6 are drawn
04400	several preliminary conclusions about both the utility of the  BEINGs
04500	representation and about problems relevant to Automatic Programming.
04600		The  appendices  present  further   details,   samples,   and
04700	examples.   First  comes  a  description  of  each BEING part, then a
04800	summary of the knowledge contained in each BEING.  Appendix  3  is  a
04900	table  of data recording how the BEING community interacts. The final
05000	appendices  present  excerpts  from  the  CF   program,   from   PUP6
05100	synthesizing CF, and from CF itself running.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY:  IDEAS)
00300	⊗23. THEORY:  IDEAS⊗*
00400		How should knowledge be represented?  Many  researchers  feel
00500	that a simple, uniform formalism should be used for all facts; others
00600	disagree, claiming that complexity of  behavior  both  justifies  and
00700	demands complexity of representation.  The BEINGs concept may resolve
00800	this uniformity vs.  structure controversy; at the  least,  it  is  a
00900	compromise.  One  must  recognize  the  advantages  of each side, and
01000	refuse to give them up. The  benefits  of  the  former  include  easy
01100	addition  of  knowledge  [Newell]  and  simple, aesthetic methods for
01200	combining information [McCarthy]. Structure,  however,  is  necessary
01300	for (⊗4combinatorially⊗*) efficient handling of large amounts of data
01400	(see the real world; also
01500	[MIT]). PUP6 integrates these two ideas into the concept of BEINGs. A
01600	BEING  is  a  collection  of  about  thirty  little bits of INTERLISP
01700	[Teitelman] code; the answers to thirty questions  about  the  BEING.
01800	That  is,  a  BEING  is  a small, loosely-knit LISP program, which is
01900	considered equivalent to its answers to these fixed questions.  Every
02000	scrap  of knowledge and all control structure should be encoded
02100	into BEINGs. There should be nothing else  in  the  system  but  this
02200	interacting community.
02300		PUP6  embodies  only  some  of  the  ideas  and   constraints
02400	discussed  in  this section.  For example, economy demanded some very
02500	fast auxilliary functions, demons, and pure  data  structures.  These
02600	reduced  the  computation  time  by a constant factor (about ten), by
02700	saving on the overhead implicit in each call to a BEING; they did not
02800	therefore  reduce the ⊗4combinatorial⊗* effort involved. This will be
02900	explained in the REALITY section, along with any other deviations  of
03000	PUP6 from an ideal BEINGs community.
03100		Notice that while  each  BEING  is  highly  structured,  this
03200	structure is standard over the entire pool. Each BEING part is itself
03300	a little BEING, etc.,  and  this  infinite  regress  stops  when  the
03400	contents  of  a BEING part becomes sufficiently primitive. As will be
03500	discussed later, the BEINGs mimic a  human  programmer;  whatever  he
03600	considers primitive  when  writing  the  program, BEINGs may consider
03700	primitive.  Typically this level is about the same as  the  INTERLISP
03800	language:     a primitive is a single INTERLISP function
03900	call, or a  few  simple  ones  connected  trivially.  Each  BEING  is
04000	cognizant  of  the  set  of  thirty  questions,  in the sense that in
04100	answering one of them it may freely ask  questions  of  other  BEINGs
04200	(often  through  nondeterministic  goal  statements.)  A  few  of the
04300	BEING-PARTS might be:     what is your basic idea and  purpose,  what
04400	effects  do  you have, how do you go about causing them, what must be
04500	ensured before you begin, how  complicated  are  you,  what  is  your
04600	chance  of  success, are  you recursive, whom else might you transfer
04700	control to, what alternatives to you exist, what BEINGs are a  little
04800	more/less  general than you are, do you evaluate your arguments, what
04900	is the nature of the value you return, why do you exist, why  do  you
05000	want  to  be  in  control  now, etc. The reader may wish to glance at
05100	Appendix 1, to  see  the  particular  set  of  questions  which  were
05200	actually  settled  upon.   When  he  feels  the  urge  for a concrete
05300	example, he should glance over pages 11-12 and Appendices 4 and 5.
05400		The delineation of this set of questions has much to do with
05500	the epistemology of programming.  The BEING parts may be classified
05600	according to their usage.  Each BEING part has two tasks: it may be
05700	⊗4asked⊗* about something, and it may be ⊗4called⊗* on to do 
05800	something. Each of these may involve asking and calling other parts
05900	of itself and of other BEINGs, but typically the second activity
06000	involves an extra level of evaluation. Some parts are relevant to 
06100	only one of these functions; most are at least oriented more toward
06200	one than the other. For example, the ARGS part may be asked trivial
06300	questions about the arguments to the BEING, but its main role is to
06400	bind the arguments when the BEING is given control. In Appendix 1,
06500	the role of each part is described. The ask-oriented parts divide
06600	into categories based on why they are queried: to decide which BEING
06700	to pass control, to tell whether the BEING has a certain property, or
06800	to give a memorized English answer to the user under proper stimulation
06900	(examples of these three types are: WHEN, PREDICATE, WHAT).
07000		The BEINGs control themselves in a simple way. A very general
07100	BEING, SERVE_THE_USER, has control initially. In general, some  BEING
07200	⊗4B⊗*  will  be  in  control.   Its BEING parts are assembled into an
07300	executable function, and it is run.  During the course of its  reign,
07400	⊗4B⊗*  will  want things done and/or tested which it cannot manage by
07500	itself.  This corresponds to when a normal program needs  to  call  a
07600	subroutine.  What ⊗4B⊗* does is to call on SATISFY by name, supplying
07700	a description of what is wanted.  SATISFY assembles itself, asks  the
07800	entire  BEING  pool  "who can do this thing?", and collects a list of
07900	the reponders.  SATISFY then calls  CHOOSE_FROM  by  name,  supplying
08000	this  list  and  the original request. Each responder is asked why he
08100	should be allowed to go now (the WHEN part) and how costly he will be
08200	if he does go (the COMPLEXITY part.) The best responder BEING is then
08300	passed control. If  he  succeeds  in  his  mission,  SATISFY  returns
08400	control to ⊗4B⊗*. Otherwise the remaining responders are compared and
08500	a new one is tried. If they all fail, then SATISFY tells  ⊗4B⊗*  that
08600	it has failed. ⊗4B⊗* then decides whether to try something else or to
08700	fail itself. In addition to these goal  statements,  there  exists  a
08800	"world" consisting of assertions and variables with values. These are
08900	regarded as trivial cases of BEINGs, possessing only  one  part.   So
09000	⊗4B⊗*  may also query this data base by saying "what assertions match
09100	this one...", or by asking "what is the value of...".  These  actions
09200	can be programmed in a much more efficient manner than as BEINGs.
09300		The CHOOSE_FROM and SATISFY BEINGs act as global schedulers, and
09400	detract from the equality proclaimed earlier for each BEING. This again
09500	touches on the philosophy of programming. Since the parts which reflect
09600	how desirable a BEING is at any given time are standard over all BEINGs,
09700	the mechanism for choosing the control successor will be about the same
09800	whoever is in control. Either this choice algorithm must be duplicated
09900	inside every BEING, or else a universal chooser BEING must be tolerated.
10000	It seems that one must have either duplication of knowledge or else 
10100	factor out the common knowledge into some higher-level interaction
10200	BEINGs.
10300		Theory would indicate that BEINGs must be assembled by  other
10400	BEINGs dynamically. In practice, the way a BEING's parts fit together
10500	is uniform over all the BEINGs at all times. Thus one simple function
10600	(or  assembled BEING) can assemble all the BEINGs initially into LISP
10700	functions.  The precise algorithm for doing this is discussed in  
10800	section 4.2.
10900		BEINGs are the only  entities  permitted  (theoretically)  to
11000	exist in our system; ergo all our code must be written as BEINGs, and
11100	must be written by BEINGs.
11200		An  obvious but crucial consequence is that ⊗4some⊗* BEING(s)
11300	must write new BEINGs. The significant point is 
11400	that the BEING  who  knows  about
11500	⊗4X⊗*  takes  charge  of  generating  BEINGs  relating to ⊗4X⊗*.  For
11600	example,  the  INSERT  BEING  can  do  inserting  by  one  of  a  few
11700	algorithms,  and  he  can  also  write (by specializing himself) more
11800	specific  insert  routines,  and  he  can  answer   questions   about
11900	inserting. This idea is analogous to any reliance upon experts (e.g.,
12000	[Feigenbaum]), and also reemphasizes the theme of any modular
12100	representation of knowledge.
12200		A second consequence is that the output code  will  have  all
12300	the ⊗4types⊗* of "intelligence" that any BEING community has:      it
12400	can write variations of itself, modify itself according to the user's
12500	complaints,  and  answer questions about what it is doing as it runs.
12600	The specialized code cannot, of course, write the full complement  of
12700	programs the original system could write.
12800		In a similar vein, ⊗4some⊗* BEING(s) must do the  translation
12900	of  the  users' quasi-English inputs into BEING-usable form. ↓_Each_↓
13000	BEING ⊗4X⊗* is charged with recognizing English related to  ⊗4X⊗*.
13100	Thus  translation
13200	consists  of  querying  "who  can  recognize  ..."  and waiting for a
13300	response. For example, our  INSERT  BEING  must  also  recognize  and
13400	process phrases involving inserting, stack-pushing, and merging.
13500		A result of this treatment of natural language
13600	processing is that any phrase which can be translated can be acted
13700	upon, and any phrase which can't be translated probably ⊗4can't⊗*
13800	be acted upon (even if it is rephrased).  Since patterns are used,
13900	if the global structure of the sentence is recognized, then the user
14000	need only be asked to clear up the difficult sub-parts.
14100		Three constraints are present which reflect new biasses  more
14200	than  new  insights:       one need not feel any reverence toward the
14300	exploratory anthropomorphic paradigm of programming 
14400	(ignore details,  catch  them
14500	later by debugging).  As in all programming, 
14600	decisions continually crop up which
14700	the system is not able to resolve  at  the  time. The  BEINGs  system
14800	should  always  spend  a significant effort deferring the decision as
14900	long as possible.  When, at last, no progress can be made without its
15000	resolution,  and  if the system is still unsure, then either the user
15100	settles the question or else a backtrack point is reluctantly set up.
15200	"Reluctant" means that it is the last of several alternatives which
15300	are tried.
15400	But  often,  by  this  time,  some  new  information is present which
15500	enables the system to resolve the decision, thus reducing the  amount
15600	of  backtracking.   If  there  are two or more decisions which can no
15700	longer be deferred, the system tackles first the one estimated to  be
15800	the easiest (analogous to Occam's razor).
15900		The final prejudice is that most of the  carelessness
16000	bugs  can be eliminated through this deferral, feed-forward, and very
16100	precise  record-keeping.  Humans  depend  on  their  adaptability  to
16200	compensate  for limitations in their brain hardware (long write times
16300	for long-term memory and  external  memory,  and  limited  short-term
16400	memory size force us to ignore details; see [Newell]) but there is no
16500	need for an ⊗4automatic⊗* programming system to do so.  For  example,
16600	when  a  list  structure  is  first  encountered,  the system records
16700	warnings that it is undefined, no accesses, insertions, or  deletions
16800	have  been  observed,  and  so  on.  Each such worry is weighted, and
16900	periodically the system resolves such  warning  notes  --  especially
17000	near the completion of the target program.
17100		To understand why Automatic Programming is a good task for a
17200	BEINGs pool, it is necessary to defocus our interest momentarily.
17300	The BEINGs representation may be  suitable  for  simulating  any
17400	complex  task ⊗4T⊗* involving frequent small interventions by various
17500	experts. In addition to writing programs, this activity could  
17600	perhaps be  as
17700	diverse  as  playing  chess,  running a business, simulating physical
17800	interactions,  and  playing  volleyball.  For  the  latter  task,   a
17900	BEINGs-based system might create a specialized BEING for each player,
18000	perhaps with a complexity vector indicating his abilities,  reflexes,
18100	etc.  The  BEING  in  control would be the player hitting the ball. A
18200	specialized  Choose-from  BEING   would   decide   who   goes   next,
18300	occasionally interpreting a tie between BEINGs vying for control as a
18400	collision on the court.
18500		There  is  one  particular  bias  of  BEINGs  toward  writing
18600	high-level programs, over other activities. The  new  BEINGs  created
18700	during  the  execution of a specified task are kept distinct from the
18800	original set  of  BEINGs.  Then  a  ⊗4program⊗*  for  task  ⊗4T⊗*  is
18900	accomplished  by doing ⊗4T⊗* and then dumping the new BEINGs out onto
19000	a new file.  The entire old  BEINGs  pool  is  then  treated  as  the
19100	language  supporting this file. As a corollary, asking a BEINGs-based
19200	system to write any subset of itself is the null task!
19300		Most  programmers  intentionally augment their code to aid in
19400	later debugging, modification, and readability by humans.  These aids
19500	are  typically  comments,  summaries,  over-generalized  subroutines,
19600	optional print statements,  and  runtime  statistics.  Recently, the
19700	structure  of  the  program  itself has also been
19800	recognized as a powerful
19900	manipulable element, affecting the accessability of the code, not just
20000	its length or running time.
20100	The length of any program written as a pool  of
20200	BEINGs  is several times as long as a clean hand-coded version.  This
20300	extra code, the parts of each new BEING which are superfluous, may be
20400	viewed as well-organized self-documentation.  They should improve the
20500	debugging, expansion, and  accessibility  (to  alien  users)  of  the
20600	synthesized code.
20700		Some assertions are so meaningful  to  the  user,
20800	that they should be stored in the code itself, even if they are
20900	only temporary.  At any time, the user
21000	may look at a piece of code; the comments present  ⊗4then⊗* are  all
21100	assertions pertaining to that piece of code at that time.
21200	BEINGS may use comments at  several  different  levels.  At  the
21300	lowest  level,  each  comment  is  merely  a  unique token; it may be
21400	inserted, removed, or searched  for.   Slightly  better,  the  BEINGs
21500	system can ask "is there a comment involving ...". For this purpose, a
21600	constrained syntax for the comments should be developed. Otherwise
21700	(as, unfortunately in PUP6) each new comment must be attended to
21800	ad hoc.      Still higher level
21900	usage of comments would occur if a BEING looked at a comment  totally
22000	ignorant of it, and TRANSLATEd it into something meaningful. 
22100		When imagining an ideal AP  (automatic  programming)  system,
22200	one  ability  we  might  wish  for  is  that  it  be  able to input a
22300	well-documented program, glean pure programming knowledge from it,
22400	and  transform  this  into  a  format  it  can use.  Also, to improve
22500	itself, it should be capable of digesting a sample, valid AP  dialog,
22600	and (perhaps through additional user interaction) modify itself so it
22700	could actually carry on that  dialog.  
22800	Another ideal to hope for is that the user be permitted to do whatever
22900	he can whenever he can; if he suddenly thinks of a stray caution, the
23000	AP system should accept it (e.g., "Oh, I might want to type in 
23100	HALT instead of STOP, sometimes").
23200	BEINGs were not designed with
23300	these ideals in mind, and as a result they may be an
23400	insufficient framework for achieving this.
23500	By studying the difficulties of the implementation of the BEINGs
23600	ideas, isolating those due to poor programming from those due to
23700	poor ideas, enough may be learned to build the next system one
23800	qualitative step closer to this ideal.
23900		It is in this spirit that BEINGs
24000	are now contrasted against  the  concepts  of  ACTORs, CLASSes,
24100	FRAMES, HACKER, formal AP systems, and macro expansion schemes.
24200		ACTORS [Hewitt]  provided  the  key  concept  of  integrating
24300	uniformity  of  construction  with  sophistocation of behavior. There
24400	is a continuum, among modular knowledge schemes, of standardization of
24500	"message" types between modules. ACTORs have no restriction whatsoever
24600	on this format. Each module has its own, unique parts (types of
24700	answers). So each ACTOR must be aware of all the parts (message formats)
24800	of all the  ACTORs it ever is going to communicate with. 
24900	Adding a new module is thus conceptually intricate as
25000	well as practically difficult. CLASSes [..........] have a few standard
25100	parts, and the modules are arranged in groups, each of which has its
25200	own additional types of parts. Thus a module can ask ⊗4any⊗* other module
25300	one of a few universal questions, and it can ask any module in its group
25400	an additional set of questions. If it is permitted to know about other
25500	groups' special parts, then the same adding problem recurs. If it is
25600	denied such knowledge, it cannot access much of the knowledge in the
25700	pool.  If one requires a completely universal set of message types, then
25800	most of them will be irrelevant to most modules. This is the price which
25900	BEINGs pay. Later, it will be shown that this superfluity is real and is
26000	marginally tolerable. The most devastating criticism of striving for a
26100	universal set of module questions is that all this does is push all the
26200	non-uniformity down into the values of these parts. The only retort is
26300	empirical: if a good partitioning of the questions can be found, then
26400	the internal structure of each part with the same name will be comparable,
26500	and the only communication necessary will be simple questioning of
26600	modules's parts.
26700	
26800		FRAMES [Minsky] seems superficially similar  to  BEINGs,  and
26900	are so amorphous that they actually could subsume BEINGs. There is a
27000	deep difference of philosophy and of intended usage, however.
27100	FRAMES intentionally have default values already (with no processing)
27200	filled in  for each frame, and replaced only when  necessary.
27300	This  is  akin  to  automatic  programming by blind debugging, but is
27400	antithetical to the fastidious bookkeeping BEINGs philosophy.  As  an
27500	example,   consider   the   writing   of  a  short,  recursive,  list
27600	manipulation LISP program (reverse, flatten, assoc, alternate,  etc.)
27700	A human, consulting the proper frame in his head, knows to ignore the
27800	base step for a while, then fill it in, usually  as  ⊗4if  NIL,  then
27900	NIL⊗*.  The
28000	human makes this default synthesis, tries out the program, and  looks
28100	closer  (to fill in this "slot" properly) only if something calls his
28200	attention to it (such as a LISP error message:
28300	NON-NUMERIC ARG  ⊗4NIL⊗*, e.g., if what was really needed was the base
28400	step ⊗4if NIL, then 0⊗*).
28500	A BEINGs system would
28600	also  defer working on the base step, but could -- and would -- place
28700	a note about that deferral into the assertional warning base.  Before
28800	thinking  it  was  finished,  the  system  would  attend to that note
28900	carefully. This is not a criticism of FRAMES:   
29000	they  are  meant  to  be  a
29100	construct  to  model  perception,  and  therefore the default concept
29200	makes sense for them. BEINGs are clearly non-anthropomorphic in their
29300	internal  workings,  and  would  be very awkward models of human
29400	perceptual mechanisms.
29500		HACKER [Sussman] differs from BEINGs in the same  qualitative
29600	way as FRAMES do.  
29700	The orientation of HACKER is to put together pieces of programs
29800	into something close to the final desired target, then  try  and  run
29900	it.  When  errors result, they are analyzed and then patched.  BEINGs
30000	is oriented toward writing bug-free code; what it writes must  always
30100	coincide  with its internal specifications of that code. The user may
30200	later change his mind, and a BEINGs system must be able to modify its
30300	own  programs,  but  this  process  is much better defined than blind
30400	debugging. On the other  hand,  if  a  BEINGs  system  does  have  an
30500	unexpected bug in it, it may not be able to recover from it. One
30600	way to overcome this would be to include special recover-from-bugs
30700	BEINGs.
30800		The  formal  manipulation  systems which also synthesize code
30900	are so different from BEINGs, that it is difficult to  compare  them.
31000	These  logical systems (e.g., [Luckham]) attack an entirely different
31100	problem.  Their task is specified rigorously  in  advance,  and  they
31200	proceed  formally  to  search  for  a  solution  program.  BEINGs are
31300	designed to work on a much higher level, heuristically.  Each  action
31400	is  implicitly justified by the fact that the user can later describe
31500	to the system
31600	what is undesirable about the program it's generated. BEINGs  should
31700	thus  be  tolerant of user ambiguity and error.  Also, BEINGs are not
31800	limited to automatic programming.
31900		Like  ⊗4any⊗* AP system which writes structured programs, the
32000	external behavior  of  a  BEINGs  system  applied  to  this  task  is
32100	reminiscent  of  macro  expansion regardless of ⊗4what⊗* the internal
32200	BEING  interactions  are.  One  major  distinction  between  the  two
32300	concepts is when and how the macros are expanded. Traditional answers
32400	are:  at  compile  time,  by  rigid   substitutions.
32500	BEINGs  systems expand their "macros" at
32600	times they choose, using knowledge gleaned from each other  and  from
32700	the  user. For example, consider a series of macro calls occurring in
32800	the code: (m1)(m2)(m3). A macro expander could expand these in any order,
32900	and the three activities could go on simulatneously, with no interference
33000	or change in the final code. BEINGs would try to find some task common
33100	to all three calls, and work on that first. The order of which to
33200	first expand fully would be carefully weighed, 
33300	and during that expansion new
33400	information would be learned which could affect the expansions of the
33500	other two function calls. The final code would not simply be the APPEND
33600	of the expansions of m1, m2, m3.  As macro expansion schemes increase
33700	in sophistocation, it may someday be appropriate to refer to BEINGs as
33800	such a system.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY:  EXAMPLES)
00300	⊗24. REALITY:  EXAMPLES⊗*
00400		This  section  presents  examples  of  the following:       a
00500	programming knowledge BEING, an explanation of what  happens  when  a
00600	BEING  is called, a concept formation knowledge BEING, a description
00700	of a piece of the user-PUP6  dialogue,  and  some  justification  for
00800	using functions, call-by-name, demons, and assertions. Although these
00900	examples are meant to clarify  the  preceding  section's  theoretical
01000	ideas, they are all drawn from the actual PUP6 system.
01100		4.1.   OBTAIN_USABLE_INFORMATION  is  a  typical  high-level,
01200	domain-independent  BEING.    The  WHEN  part  consists  of predicate
01300	"feelers"  which  sample  the  world  and  report   their   qualities
01400	numerically.   A reason is supplied with each feeler:
01500	an English sentence stored for the benefit of inquisitive users.
01600	The numbers are
01700	then simply added to decide how a propos the  BEING  is  at  present.
01800	This  scheme  is  adequate  but  undesirable;  one would like them to
01900	discuss descriptions of what they encounter; but  the  WHEN  part  is
02000	used  only  to  break  ties  between BEINGs vying for control, and it
02100	usually doesn't matter what order they go in.  Thus  a  simple,  fast
02200	method  of  selection suffices.  This particular BEING (whose parts
02300	are exhibited on pages 11 and
02400	12) has feelers which respond that it is ⊗4always⊗* an  undesirable
02500	(-10)  thing  to  do, but ⊗4may⊗* be indicated (+111) if there exists
02600	new but not yet usable information. The possible final WHEN
02700	values are thus 111, 101, and -10. These numbers, like all the parts
02800	of all the BEINGs initally in PUP6, were decided upon and inserted by
02900	hand.
03000		The   IDEN   parts   are  collected  together  into  a  large
03100	translation table.  When  a  form  ⊗4LI⊗*  must  be  translated,  the
03200	TRANSLATE  BEING goes through this table, asking each IDEN part if it
03300	claims to recognize ⊗4LI⊗*. Each IDEN runs its  own  little  program,
03400	typically  some  type of pattern match involving ⊗4LI⊗* and the state
03500	of the world, to answer this question.  Some measure of  goodness  of
03600	match  is  also  reported.   If  there  is  more  than one responder,
03700	CHOOSE-FROM picks the one with the highest priority of  match.    The
03800	winner runs a little program which ultimately returns a BEING-call or
03900	a constant as the translated value of ⊗4LI⊗*. This program might call
04000	other  BEINGs,  often  calls  TRANSLATE  several times recursively on
04100	parts   of   ⊗4LI⊗*.     Now   examine   the   IDEN   part   of   the
04200	OBTAIN_USABLE_INFORMATION  BEING  (next page).
04300	There are just two classes of phrases that this BEING can recognize.
04400	If two conditions are met,
04500	it says to ⊗4call⊗* OBTAIN-USABLE-INFORMATION with, as argument,  the
04600	result of calling TRANSLATE on the second element of ⊗4LI⊗*.
04700	If some BEING or user wants to find out more about anything, then 
04800	this BEING can be called with that thing as argument.
04900		The EFFECTS parts of each BEING are similarly collected  into
05000	one  table  to  facilitate  asking all BEINGs simultaneously "Can you
05100	cause X to occur?" Each EFFECTS part examines X and  the  world,  and
05200	either  replies No, or else returns a little program (involving calls
05300	and constants) which  should  produce  the  effect,  with  a  certain
05400	probability.   This program will probably involve a call to the BEING
05500	itself. The BEING below shows that it should be called to acheive the
05600	existence of new, usable information (see the MAIN:EFFECTS part, page
05700	12).
05800		The WHAT, HOW, and  WHY  parts  are  mainly  for  the  user's
05900	benefit.   When  a  choice  between  BEINGs  must  be made, the WHEN,
06000	AFFECTS,  and  COMPLEXITY-VECTOR  parts  are  queried.    If  a  new,
06100	manipulated   version   of   the   BEING   must   be   created,   the
06200	SPECIALIZATIONS,   ENCODABLE,    DATA-STRUCTURE,    PREDICATE,    and
06300	FORM-CHANGING  parts  might  be  relevant.   If the BEING fails, some
06400	BEING speicified in the ALTERNATIVES or GENERALIZATIONS parts might
06500	be tried.
06600		In the current case, the COMPLEXITY-VECTOR says that it is of
06700	average difficulty to call, its descendants may (.5 chance)  call  it
06800	back,  it has an average chance of success and cost of attempting it,
06900	and there is no (.1) good reason to defer it any longer.
07000		The  AFFECTS  part  of the OBTAIN_USABLE_INFORMATION BEING is
07100	clear. One BEING is definitely called, and four others might be. 
07200		The  absence  of  some parts, like DATA_STRUCTURE, PREDICATE,
07300	and NLAMBDA, indicate that these qualities don't apply.  The  absence
07400	of  other  parts,  like  SPECIALIZATIONS and ALTERNATIVES, indicate 
07500	only a
07600	lack of thoroughness in filling out unneeded BEING parts.
07700		The   META-CODE  says  to  choose  from  the  following  four
07800	alternatives,    each    of    which    is    itself     a     BEING:
07900	Get_Brand_New_Information  (in  English,  from  the  user), Translate
08000	something    (transform     from     English     to     BEING-calls),
08100	Analyze_The_Implications  (of some existing, translated information),
08200	Extract_a_Relevant_Subset   (of   the   existing   information)    to
08300	concentrate upon.
08400	Calls are nondeterministic only when the BEING doesn't know exactly
08500	which BEING to call. If the ⊗4set⊗* of possible choices is known, as
08600	in this case, then CHOOSE-FROM is called with the choice set explicit.
08700	If even this isn't known, then CHOOSE-FROM must query the EFFECTS
08800	parts of all the BEINGs in the system.
08900		Below are exhibited the actual representation of  this  BEING
09000	in  PUP6,  and  the  function  which  would  be  executed  if it were
09100	⊗4called⊗*.
09200	
09300	.SELECT 5
09400	.BEGIN NOFILL
09500	
09600	
09700	⊗4↓_PART_↓    ↓_actual value of the part for OBTAIN:USABLE:INFORMATION_↓ ⊗*
09800	
09900	IDEN ((if you see: (AND (EQUAL (CAR LI)
10000		  		    	OBTAIN:USABLE:INFORMATION)
10100		 	        (EQUAL (LENGTH LI)
10200					 2))
10300	       then return: (OBTAIN:USABLE:INFORMATION (TRANSLATE (CADR LI))))
10400	      (if you see: (MATCH ( FIND OUT MORE ABOUT ANY1)   LI)
10500	       then return: (OBTAIN:USABLE:INFORMATION ANY1)))
10600	BEING T 
10700	EXPLICIT:ARGS (U) 
10800	WHAT ( OBTAIN SOME INFORMATION WHICH CAN BE USED) 
10900	HOW ( OBTAIN NEW FACTS ABOUT OLD INFORMATION, OR OBTAIN TOTALLY
11000	     NEW INFORMATION) 
11100	WHY ( PUP HAS NO MORE INFORMATION THAT IT CAN USE TO PROGRESS) 
11200	WHEN ((if T then add in -10 (SINCE THIS IS AN EXPONENTIALLY-GROWING,
11300		      			BAD THING TO DO IN GENERAL))
11400	      (if NEW:INFO:LIST then add in 111
11500	             	(BECAUSE WE SHOULD WORK ON UNASSIMILATED NEW 
11600		                      INFORMATION IF THERE IS ANY)))
11700	META:CODE (DO
11800			 (CHOOSE:FROM ((TRANSLATE U)
11900	   			       (GET:NEW:INFORMATION U)
12000				       (ANALYZE:IMPLICATIONS U)
12100				       (EXTRACT:RELEVANT:SUBSET U)))
12200		   BECAUSE
12300			 (WE CAN ONLY TRY TO OBTAIN USABLE 
12400				    INFORMATION IN ONE WAY AT A TIME))
12500	EXPLICIT:ARGS:CHECK T 
12600	MAIN:EFFECTS ((to get (NEW INFO ANY1)
12700	               do (OBTAIN:USABLE:INFORMATION ( ANY1)))
12800	              (to get (USABLE INFO ANY1)
12900		       do (OBTAIN:USABLE:INFORMATION ( ANY1)))) 
13000	AFFECTS       ( (CHOOSE:FROM CALLED)
13100		        (TRANSLATE POSSIBLE:CALLED)
13200	 	        (GET:NEW:INFORMATION POSSIBLE:CALLED)
13300		        (ANALYZE:IMPLICATIONS POSSIBLE:CALLED)
13400		        (EXTRACT:RELEVANT:SUBSET POSSIBLE:CALLED) )
13500	COMPLEXITY:VECTOR (.5 .5 .5 .5 .1) 
13600	
13700	.SELECT 1
13800		4.2. When a BEING is ⊗4called⊗*, its parts are assembled into a
13900	function which is then executed. Here is the ⊗4FUNCTIONAL⊗* form of the
14000	OBTAIN:USABLE:INFORMATION   BEING:
14100	.SELECT 5
14200	
14300	(OBTAIN:USABLE:INFORMATION
14400	  (LAMBDA (U FN:VALUE FINAL:CO:REQ)
14500	      (PROG1 
14600	          (AND 
14700	              (SETQ BEING:STACK (CONS OBTAIN:USABLE:INFORMATION BEING:STACK))
14800	              (PUT OBTAIN:USABLE:INFORMATION SPEC:WHY BECAUSE)
14900	              (EVERY (APPEND CURRENT:DEMONS USER:INTERRUPT:DEMONS)
15000	                     (QUOTE APPLY*))
15100	              (SETQ BECAUSE
15200	             	   (QUOTE (WE CAN ONLY TRY TO OBTAIN USABLE 
15300	                              INFORMATION IN ONE WAY AT A TIME)))
15400	              (CHOOSE:FROM (QUOTE ((TRANSLATE U)
15500	           		           (GET:NEW:INFORMATION U)
15600				           (ANALYZE:IMPLICATIONS U)
15700				           (EXTRACT:RELEVANT:SUBSET U)))))
15800	          (SETQ BEING:STACK (CDR BEING:STACK)))))
15900	.END
16000	.SELECT 1
16100	
16200		The  process of assembling the BEING parts into a function is
16300	straight-forward.  First, the explicit arguments (those global to the
16400	BEING)  are  bound. The implicit arguments (those local to the BEING,
16500	like PROG variables) are initialized. The name of the BEING is pushed
16600	onto  the  BEING  control  stack  (pointing  to  its caller), and any
16700	newly-activated  demons  are  pushed  onto  the  demon  stack.   The
16800	ARGS-CHECK  predicates  are  evaluated.  Then PUP6 works to make each
16900	PRE-REQUISITE true in the world.  Each COMMENT is evaluated, then the
17000	CO-REQUISITES,  META-CODE,  and  current  demons  all are executed in
17100	pseudo-parallel.  Each POST-REQUISITE is then satisfied.  Since these
17200	activities are all embedded in an AND, any of them may cause the
17300	entire BEING to halt and fail, simply by returning NIL.
17400	In both cases, just  before  exiting,  the  demon
17500	stack is popped and the BEING stack is updated (usually just popped),
17600	and control passes to the delegated BEING (usually the one who called
17700	this  BEING,  at  the  state  when  he  called  it.)  A fancy context
17800	mechanism was available but not actually needed.
17900		The function which assembled all the BEINGs exploited the
18000	fact that it operated only at  system load time. Thus if the BEING 
18100	had no new DEMONs to activate, all the corresponding demon-stack
18200	manipulations could be omitted. Optimizations like these are clear
18300	from comparing the functional form and the description of how it
18400	should be created (see above).
18500	Another example in this BEING is that no CO-REQUISITES 
18600	occur, so no parallel processing need be simulated. 
18700		4.3. PARTITION_A_DOMAIN is a high-level, domain-specific BEING
18800	whose basic idea is to divide up a space into  categories.  Only  two
18900	BEING   parts   are   filled   in   here   which   were  absent  from
19000	OBTAIN_USABLE_INFORMATION; namely, SPECIALIZATIONS  and  DEMONS.  The
19100	SPECIALIZATIONS part says that to write a specific version of itself,
19200	a few decisions must be made. The results  will  then  indicate  what
19300	pieces  of  code  get  assembled together to form the new BEING.  The
19400	partition may be only partial (an element of the domain belongs to no
19500	class  of  the partition), only weak (an element belongs to more than
19600	one class), and, most importantly, the specialized BEING should  work
19700	by  repeatedly doing some of the following three activities: accept a
19800	class-name from the user and guess some of its elements, accept an 
19900	element from the user and try to guess which class it belongs to,
20000	or accept an <element, class-name> pair. Other BEINGs know
20100	about these accepting, guessing, checking activities.
20200		The  DEMONS  part says that during the partitioning, the only
20300	new demon to keep active is the one  called  Fringe_of_Consciousness.
20400	This was named  in parody of an "impossibility"
20500	mentioned in [Dreyfus], is worth  exemplifying.   In  the  course  of
20600	writing  GI,  the  system  learns  that  the  main  task  is  one  of
20700	grammatical inference.  The Grammatical_Inference BEING then  asserts
20800	that  if  the  user ever mentions the word TEST, he may actually mean
20900	PARSE.   This is placed in the IDEN part of the TEST  BEING,  and  is
21000	therefore   only  demonized,  waiting  on  the  periphery  of  PUP6's
21100	concentration.   It is in fact triggered later in the dialogue, as an
21200	inference surprising to the user.
21300		4.4.  The dialogue to synthesize CF begins by PUP6 asking the
21400	user  for  any  task.   The user replies, ⊗4Write a program which does
21500	concept formation⊗*. There are many decisions that PUP6 knows about in
21600	writing  a  specialized  concept formation program [Hempel], 
21700	and it manages to
21800	defer them all.   For example, it must choose between classificatory,
21900	comparative,  and metrical concept formation. Since all three involve
22000	partitioning a domain of examples, PUP6 decides  it  can  defer  this
22100	choice  until  after code for the partitioning is synthesized.    The
22200	effort of the system is now  directed  toward  this  "piece"  of  the
22300	program.  When it is completed, an hour or two later, the system asks
22400	the user to make this decision. When he picks the first  alternative,
22500	which  involves ⊗4only⊗* partitioning,  the  system  prints that it has
22600	finished the entire CF task, and dumps the newly created BEINGs  onto
22700	a file.
22800		4.5. Earlier, the claim was made that the presence of popular
22900	AI language  features did not detract from the combinatorial behavior
23000	of the system, since BEINGs subsume each mechanaism used. This will
23100	now be sketched. Direct call by name may be viewed as a trivial type
23200	of pattern-directed call, 
23300	where each BEING can recognize its own name. See the IDEN part of the
23400	OBTAIN:USABLE:INFORMATION  BEING, for example.
23500		A demon
23600	in PUP6 is merely a function which gets executed periodically,
23700	and may occasionally trigger a BEING. This could  be  replaced  by  a
23800	BEING   whose   EXPLICIT:ARGS:CHECK   part  contains  the  triggering
23900	predicate, and whose META:CODE is simply a call by name  directly  to
24000	the  BEING  which  is  supposed to be activated.  
24100		An assertion can be
24200	viewed as a BEING containing  only  an  IDEN  part;  when  the  BEING
24300	recognizes a form which matches it, it returns the fully instantiated
24400	assertion. 
24500		A function is equivalent to a BEING with only  META:CODE, 
24600	ARGS, and NLAMBDA
24700	parts;  one  knows almost  nothing about it before executing it.  
24800		Notice that
24900	the overheads saved by these mechanisms are substantial. For example,
25000	assertions replace an entire BEING call by a single CDR evaluation.
25100		The reader may have observed  the  static  quality  of  these
25200	examples,  and  wished  for  one of BEINGs in action, passing control
25300	back and forth in order to do something. But to present a  reasonable
25400	example   of  BEINGs  interacting,  it  is  necessary  to  understand
25500	something about the target  task.   Thus  we  describe  PUP6  in  the
25600	following  section,  including  how  the target task CF evolved. Then
25700	comes the dynamic example, in section 6.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY:  DESIGN)
00300	⊗25. THEORY:  DESIGN⊗*
00400		A  highly  polished  presentation  of  a  large  system omits
00500	mention  of  the  design  and  implementation  mistakes.    This   is
00600	unfortunate;  many  decisions  which seem arbitrary are the result of
00700	painful re-working, and conversely.  The reader may  relax;  he  will
00800	find nothing polished about this treatment.
00900	
01000		Once  the  task  (automatic  program  synthesis from specific
01100	dialogue) was decided  upon,  considerable  attention  was  spent  on
01200	choosing  an  appropriate  domain  of  target  programs.  The choice,
01300	inductive inference  (II), merits  discussion.  The  obvious
01400	difficulty  appears  to  be  the complexity of the programs involved:
01500	they  are  two  orders  of  magnitude  larger  than  any   previously
01600	synthesized  programs. But there are four big attractions:
01700		(i)
01800	A  wide  range  of  complexity  exists,  from  a  one-page   sequence
01900	extrapolator   to   Meta-Dendral.
02000		(ii)   Each   increasingly
02100	sophisticated II program  uses  many  of  the  concepts  embodied  in
02200	simpler  II programs.
02300		(iii) If a super-human target program is
02400	ever written, it could itself contribute to the  field  of  Automatic
02500	Programming! (This remark is humorous in the seventies, but may be
02600	commonplace someday.)
02700		(iv)  Since people (especially those who write
02800	AI  programs) are the inductive
02900	inference experts, our reliance on  introspection  is  as
03000	valid  --  and potentially as valuable -- as chemists' protocols were
03100	to Dendral.
03200		After  studying  many  sample  programs  from  the II domain,
03300	sequence extrapolation [Pilvar] seemed the most reasonable  beginning
03400	task. It was quickly learned that this was too easy: humans have only
03500	a few techniques for extrapolating  sequences,  and  a  very  limited
03600	capacity   for   composing   them.   Thus  a  rather  rigid  sequence
03700	extrapolator writer may be capable of generating  a  large  class  of
03800	super-human programs (see section 4.2 on
03900	Sequence-Extrapolator-Writer, in [Green]).
04000		The  next  candidates  were grammatical inference and concept
04100	formation [Hempel].
04200	Determined not to choose too simple  a  task  again,  the
04300	latter program was finally decided upon.  The particular target was a
04400	variant of [Winston]. To make the goal more tractable, certain  parts
04500	of   Winston's   description   were  ignored,  namely  the  heuristic
04600	graph-matching section, and the uniformity requirement that relations
04700	on features be functionally indistinguishable from features.
04800	This last phrase means that CF may internally
04900	store (MUSTNOT (SUPPORTS a b))
05000	differently from the representation of simple 
05100	features like (TOUCHES a c).
05200		It seems instructive now to describe how the  target  program
05300	should operate. It repeatedly scans a scene and tries to name it. The
05400	scene is broken into a set of features and a set of objects. Each 
05500	feature is  a  relation
05600	on  one  or  more  objects  in  the  scene.  Internally,  the program
05700	maintains a model for each differently-named 
05800	concept it has ever encountered. "Concept" here is used technically, to
05900	indicate a particular data structure maintained by the target program.
06000	The  model  contains  a  description  of  the objects expected in the
06100	scene, a set of features which must be present in the scene (else  it
06200	can't  be the same as this concept), a set of features which must not
06300	be present in the scene, and a set of features which may or  may  not
06400	be  present.  Thus  a model is like an archtypical scene plus a name.
06500	Each time the program is confronted by a new scene, the program  must
06600	scan its models until it finds one which matches it. A model is said
06700	to match a scene if all the MUST features associated with that model
06800	are present in the scene, and all the MUSTNOT  features  are
06900	absent  from  the  observed scene. The target
07000	program informs the user of this guess,
07100	and accepts the proper concept name. If it  guessed  incorrectly,  it
07200	modifies its models. The wrong guess model may have features added to
07300	its MUST or MUSTNOT sets; the correct concept name model may have  to
07400	be  modified or (if it's a new concept) created and inserted into the
07500	list of models.  See the flowchart on page A4.7.
07600	.B
07700	
07800	For example, part of a scene might be:     OBJECTS a,b,c,d
07900		(GREEN a)(BLUE c)(TOUCHES c d)(SUPPORTS a c)(SUPPORTS b c).
08000	
08100	A model for an arch might be:      	   NAME    ARCH
08200	 					   OBJECTS a,b,c
08300		MUST 	(SUPPORTS a c)(SUPPORTS b c)
08400		MUSTNOT (TOUCHES a b)
08500		MAY	(GREEN a)(WEDGE c)(PRISM a)(BLOCK b)(PARALLEL a b)
08600	.E
08700		Suppose  that the target program reads in the above scene and
08800	tries to match it to  the  above  model  for  consistency.  The  MUST
08900	relations  should  all  be  present.   Yes,  the  scene  does contain
09000	(SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT  relations  must
09100	be absent from the scene. Sure enough, (TOUCHES a b) isn't there.  So
09200	the model and scene are consistent, and the program announces that its
09300	guess is ARCH.  
09400		If the user verifies this guess,
09500	then  the MAY set is augmented with (BLUE c) and (TOUCHES c d), and
09600	the OBJECTS set is augmented with "d."
09700		If the user denies that the scene is an arch,
09800	the target program
09900	sees if there are any relations in the model's MAY set which do not
10000	occur in the scene. If so, one of them (e.g., (PARALLEL a b)) will
10100	be transferred from the MAY to the MUST set.  If no such feature 
10200	existed, the program would look for a feature present in the scene
10300	but absent from all sets of the model (e.g., (BLUE c)), and insert
10400	it into the MUSTNOT set.  Also, if the user disagreed with the guess,
10500	he would be asked what the true name of the concept was, and that
10600	concept's model would have its MAY set augmented by any new 
10700	features in the scene. Any features on its MUST or MUSTNOT sets
10800	which contradicted the scene would be transferred to the MAY set.
10900		After the target concept formation program was specified,  it
11000	was trimmed and then rewritten as a structured program [Gadwa]. Next,
11100	a complete dialogue was  simulated  between  the  user  and  a  human
11200	programmer  (referred to as the system-player) playing the role of an
11300	"intelligent"  automatic  programming  system  (similar   to,   e.g.,
11400	[Balzer]).      The   system-player   kept   careful  records  as  he
11500	programmed, and tried to create a bug-free  structured  program.  The
11600	dialogue  was  then annotated:     after each user response, comments
11700	were inserted which described the "states" the system-player had gone
11800	through before printing his next response.  This included blind paths
11900	which were tried, use of outside world knowledge,  and,  in  general,
12000	was  meant  to  be  the "intelligence" necessary to do the task.  The
12100	fear was that a system could be built which synthesized  the  concept
12200	formation  program,  and  yet  was  so unintelligent that nothing was
12300	learned from it. (see section 4.1 on PW1, for example,  in  [Green]).
12400		Hopefully,  any  system  which  
12500	(i) got the target program correctly,
12600	(ii) followed this
12700	initial dialogue, and, most importantly, (iii) went
12800	through  the  same  line of reasoning that the comments indicated the
12900	system-player 
13000	followed, would be far along the road  toward  intelligence.  A
13100	corollary of this incremental annotated protocol approach is that the
13200	abilities of the user must coincide with those  of  the  subject  who
13300	participated  in the protocol (see also [Woods]). The system would be
13400	far along the road toward automatic programming if it also  (iv)  was
13500	able  to  write  CF  from several dialogues, from several users, with
13600	little preparation. PUP6 was not designed to do this, and in the  end
13700	it  proved to be a serious deficit.  Henceforth, ⊗4protocol⊗* will
13800	refer to this user-player / system-player simulated dialogue.
13900		The target user must be familiar
14000	with  LISP,  well-grounded  in  computer  science,   and   have   the
14100	input/output  behavior  of  the  concept  formation (CF) program very
14200	clearly in his mind. The natural language front  end  is  so  brittle
14300	that  the user must also phrase his responses very similarly to those
14400	of the original protocol subject.  This  factor  prevented  dialogues
14500	from multiple users from being successful.
14600	
14700		At  this  point,  most  of  the  ideas described in section 3
14800	surfaced, including a rough initial set of BEINGs.  Each one had  not
14900	much  more  than  a  name and a vague description of what it must do.
15000	The  dialogue  was  cycled  through  again,  painstakingly,  and  the
15100	comments  were  replaced  by a description of which BEINGs would call
15200	which other BEINGs, why, and the results  of  each  such  call.   The
15300	constraints   on   each  BEING  thus  grew,  sometimes  changed,  and
15400	occasionally a new BEING or  BEING  part  had  to  be  added  to  the
15500	community.  This  process  was  long  (200 hours) and produced a long
15600	(200-page) protocol, actually a hand trace of the  system  execution.
15700	About  eighty  BEINGs  were needed:  a dozen domain-specific ones and
15800	the rest  domain-independent  programming  knowledge.   About  thirty
15900	different  BEING  parts  were  called  for,  and  they  are listed in
16000	Appendix 1.  The next appendix describes each BEING briefly; only the
16100	most important knowledge is mentioned.
16200		A result of  this  method  of  incremental  specification  of
16300	BEINGs  is that each BEING has only those parts which are going to be
16400	used sometime during the ensuing dialogue. This seemed too  specific,
16500	so  some  effort  was  spent  filling out parts that weren't strictly
16600	necessary to write the  concept  formation  program.    Perhaps  more
16700	careful  attention  to  this activity would have made the system more
16800	tolerant of changes in the dialogue. 
16900		During the course  of  massaging
17000	PUP6  into  writing  the  other  target programs, very few additional
17100	parts had to be added to existing BEINGs. Typically,  either  an  old
17200	part had to be generalized or else a new BEING created. After writing
17300	CF, GI, and INF, there are now an even hundred BEINGs in PUP6.
17400		The data on how filled-out each BEING was -- and had to be --
17500	is presented in several  forms,  here  and  in  the  appendices.   In
17600	Appendix 1, next to each BEING part is the percentage of BEINGs which
17700	had to have this part specified for them. Appendix 3 reveals how each
17800	BEING  was  actually  used,  including  the number of its BEING parts
17900	which exist and were called upon during a dialogue. On  the  average,
18000	each  BEING  part  was present in 36% of all BEINGs, and, also on the
18100	average, each BEING had 10.5 of its 29 parts specified. This says 
18200	that each BEING was actually asked a third of all possible questions
18300	and that each question was needed in about a third of all the BEINGs.
18400	This is just marginally tolerable; if the percentages were much
18500	lower, then the idea of grouping the BEINGs and assigning each group
18600	its own distinct set of questions would be clearly called for.
18700		The  principle that "everything is BEINGs" was relaxed in the
18800	interests of absolute CPU time and feasibility  of  coding.   Besides
18900	BEINGs,  PUP6 employs functions, demons and an assertional data base.
19000	During  the  programming,  100  small  functions  were   written   to
19100	supplement  the  language.   Most  were  typical  current AI language
19200	features [Bobrow] (pattern-matching, demons, special data types),  or
19300	tiny additions to INTERLISP [Teitelman] (flatten, set-difference), or
19400	functions      which      manage       BEINGs       (add-a-new-being,
19500	print-a-being's-parts).   Many of these features were simplified (and
19600	speeded up) by using the knowledge that PUP6 was to be an AP  system.
19700	For  example, all the different types of assertions that an AP system
19800	might want to make deal with different concerns of programming.  Thus
19900	a  group  of about forty different assertion patterns could be fixed,
20000	each one becoming a named  list;  this  almost  eliminated  searching
20100	during retrieval from the assertional base.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY:  EXAMPLES)
00300	⊗26.  REALITY:  EXAMPLES⊗*
00400	
00500		An example of the PUP6 community of BEINGs interacting will now
00600	be presented. Let's jump one third of the way into the dialogue which
00700	writes  CF. The system learns it must compare the input scene against
00800	its internally stored models of concepts, until it  finds  one  which
00900	doesn't  fail  the  comparison.   It  asks the user what it means for
01000	scene S to fail the comparison to model M. The user  replies,
01100	whenever M  is  incompatible  with  the  observed  features  of  S.
01200	The IDEN part of the
01300	CONTRADICTS BEING recognizes this sentence pattern, and transforms it
01400	to 
01500	.NOFILL
01600	(FORSOME  F  IN M_FEATURES (specialized:contradicts F S_FEATURES)).
01700	.FILL
01800	The BEING
01900	which inserts this into the synthesized code requires that  the  user
02000	pick  some  proper  name  for  the function specialized:contradicts;
02100	this will be a streamlined contradiction test written by the
02200	CONTRADICTS BEING.  Say the user reponds by calling it IMPOSS. This naming
02300	and specializing is central to BEING creation: a BEING recognizes an
02400	instance of itself, and decides either to insert a call to itself or
02500	else to insert a call to a specialized version of itself.  If any
02600	nontrivial decisions must be made, and can be settled at synthesis
02700	time, then the latter alternative is chosen.  CONTRADICTS is too 
02800	general a BEING to be called in an inner loop, so its content will
02900	be hammered out at synthesis time. On the other hand,
03000	FORSOME is so primitive that no  specialized
03100	version  of  it  is  written normally. 
03200		Here is the way this piece of the dialogue actually appears.
03300	The user's reponses are italicised.
03400	The system informs the user of
03500	where it is by simulating a cursor pointing into a graph  of  program
03600	code.  This  is  analogous  to  the textual and dynamic indices which
03700	[Dijkstra] suggests.
03800	.NOFILL
03900	
04000	PLEASE TYPE IN A LOGICAL EXPRESSION WHICH IS TRUE WHEN WE TERMINATE
04100	       THE LOOP, AND IS FALSE OTHERWISE.
04200	
04300	SHOULD I DISCUSS RAMIFICATIONS?⊗4NO⊗*
04400	
04500	USER: ⊗4(ANY FEATURE IN MODEL:FEATURES IS INCOMPATIBLE
04600	    WITH SCENE:FEATURES)⊗*
04700	
04800	PUP WANTS USER TO TYPE IN NAME FOR  SPECIALIZED VERSION OF CONTRADICTS.
04900	
05000	USER: ⊗4IMPOSS⊗*
05100	.FILL
05200		Later in the  dialogue,  PUP6  decides  it  must
05300	expand the function IMPOSS. The CONTRADICTS BEING is again called on; this
05400	time  it  is  asked  how  to  write  a  specialized  version   of   a
05500	contradiction  test.  It  replies that SOME_OF the following types of
05600	contradiction  may  occur:        PROBABILITY:0,  PROBABILITY:1,  and
05700	PROBABILITY:ε(0,1).    This   is   the  germ  of  the  idea  for  the
05800	MUSTNOT/MUST/MAY categorization of features. The SOME_OF BEING  takes
05900	control,  and  asks  if  the  decision can be deferred.  The DEFERRAL
06000	BEING looks about, first asking if there is  any  non-null  piece  of
06100	code  that  all three have in common.  This fails, and eventually the
06200	DEFERRAL BEING reports failure.  SOME_OF sees it has  no  basis  upon
06300	which  to  form  a  guess,  and  wants somebody to ask the user.  The
06400	ASK_USER BEING takes over, and trivially finds out what exactly it is
06500	that PUP6
06600	wants  to  learn.  The names of the three choices are so cryptic that
06700	their WHAT and HOW parts are printed out to  the  user,  as  well  as
06800	their names.  The user types back his choices, in our case all three.
06900	SOME_OF  composes  three  new  function   calls,   separated   by   a
07000	conditional:
07100	.B
07200	
07300	(COND ( (IS_OF_TYPE         F   PROBABILITY:0_PART_OF_M_FEATURES)
07400		(PROBABILITY:0_CONTRADICTION    F    S_FEATURES))
07500	      ( (IS_OF_TYPE         F   PROBABILITY:1_PART_OF_M_FEATURES)
07600		(PROBABILITY:1_CONTRADICTION    F    S_FEATURES))
07700	      ( (IS_OF_TYPE         F   PROBABILITYε(0,1)_PART_OF_M_FEATURES)
07800		(PROBABILITYε(0,1)_CONTRADICTION  F  S_FEATURES)))
07900	.E
08000	TRICHOTOMY recognizes this as a split on a function's  values
08100	being  =0,  =1,  or  between  zero  and  one.   It  asks whether this
08200	particular  function  can  only  range  over  the   interval   [0,1].
08300	PROBABILITY  answers  affirmatively,  so  SOME_OF  replaces the final
08400	IS_OF_TYPE test by the constant T.  Later on, PUP6 must  worry  about
08500	the  other  two  tests, and about the three contradiction predicates.
08600	These latter entities know (their ENCODABLE  parts  tell  them)  that
08700	they  are  immediately encodable. A probability=0 contradiction means
08800	that arg1 must not occur in the  world  arg2  yet  it  does.  So  the
08900	META-CODE  of  the  PROBABILITY:0_CONTRADICTION  BEING  is defined as
09000	(MEMBER arg1 arg2).  This corresponds to a MUSTNOT feature F which is
09100	present  in  the  world  (in  the  set of S_FEATURES of the scene.) A
09200	probability=1 contradiction occurs when a feature arg1 must occur  in
09300	the  world  arg2,  yet  it  doesn't. So its definition is simply (NOT
09400	(MEMBER arg1 arg2)).  It is impossible for a feature with probability
09500	in  (0,1)  to  be  in  contradiction  with any world (lacking negated
09600	features), so this third predicate is defined as  the  constant  NIL.
09700	That  is,  if F is a MAY feature of the model M, then there can be no
09800	contradiction between F and ⊗4any⊗* features of the scene S.
09900		When a BEING is said to do or recognize or know something, as
10000	in the preceding and following paragraphs, what is actually meant  is
10100	that  one or more of its parts specificly encode that knowledge.  All
10200	the parts of the hundred BEINGs in PUP6 were coded by  hand,  not  by
10300	each  other.  They then can encode other BEINGs, interacting only via
10400	the dialogue.
10500		The  IS_OF_TYPE  BEING  recognizes  that it must work hard to
10600	replace each of the two case tests, unless  M_FEATURES  is  organized
10700	permanently  into  three  parts (thus permitting the complex function
10800	"IS_OF_TYPE" to be replaced by the simple one "MEMBER" in  the  above
10900	piece of code). The STRUCTURE_INDUCING BEING will take over, to probe
11000	the permissability and the difficulty of such a constraint.  It finds
11100	nothing  about  this  tripartite  structuring  which could damage any
11200	earlier synthesized code, and asks the  user's  blessing.  Notes  are
11300	added  to  the list of coding warnings, stating that any reference to
11400	the entire list of M_FEATURES must be replaced by  either  APPEND  of
11500	the  three  new lists, or else by three separate statements. GET_NAME
11600	is indirectly called, and he has the user name the three new sets  of
11700	features; say he responds by calling them MUSTNOT, MUST, and MAY. The
11800	system would at this point say to draw an arrow on its graph of code,
11900	from the function call (IMPOSS F S_FEATURES) to the new block of code:
12000	.B
12100	
12200	  (COND ( (MEMBER        F   MUSTNOT_PART_OF_M)
12300		  (MEMBER        F   S_FEATURES))
12400	        ( (MEMBER        F   MUST_PART_OF_M)
12500		  (NOT (MEMBER   F   S_FEATURES))
12600	        (  T (COMMENT THIS "T" REPLACES "MEMBER F MAY_PART_OF_M")
12700		   NIL))
12800	.E
12900		This is now the META:CODE part of the new BEING called IMPOSS.
13000	Most of the other parts are taken from its generalization, namely
13100	CONTRADICTS. During the course of writing this piece, however, some
13200	of these parts would be slightly changed. For example, its reason
13300	for existing would be strengthened when the simple MEMBER function
13400	calls replaced the slow IS_OF_TYPE  BEING calls.
13500	Here is the actual transcript of this part of the dialogue; it may also
13600	be seen (with the names slightly changed) in the appendix, on
13700	pages  A5.10  to  A5.12.  
13800	
13900	.NOFILL
14000	
14100	MOVE CURSOR TO  IMPOSS TYPE OF   CONTRADICTS
14200	
14300	SORRY TO BOTHER YOU, BUT I CAN NO LONGER DEFER THIS SOMEOF DECISION
14400	    (PROBABILITY=1:CONTRADICTION PROBABILITY=0:CONTRADICTION 
14500		PROBABILITY>0&<1:CONTRADICTION)
14600	SINCE THE DECISION IS SOME:OF, TYPE ANY ORDERED SUBSET OF:
14700	  (A .... PROBABILITY=1:CONTRADICTION)
14800	  (B .... PROBABILITY=0:CONTRADICTION)
14900	  (C .... PROBABILITY>0&<1:CONTRADICTION)
15000	
15100	<discussion of the ramifications of each of these types of contradiction>
15200	
15300	USER: ⊗4(A B C)⊗*
15400	
15500	(I RECOMMEND THAT MODEL:FEATURES BE STRUCTURED INTO (AT
15600	    LEAST ALONG ONE DIMENSION) THESE 3 PIECES:
15700	(PROBABILITY=1:CONTRADICTION:PART:OF:MODEL:FEATURES 
15800	 PROBABILITY=0:CONTRADICTION:PART:OF:MODEL:FEATURES 
15900	 PROBABILITY>0&<1:CONTRADICTION:PART:OF:MODEL:FEATURES).
16000	PLEASE TYPE BACK YES, NO, OR UNSURE.)
16100	
16200	USER: ⊗4YES⊗*
16300	
16400	PUP WANTS USER TO TYPE IN A SHORTER NAME FOR 
16500	  ( PROBABILITY:1:CONTRADICTION:PART:OF:MODEL:FEATURES)
16600	USER: ⊗4MUST:FEATURES⊗*
16700	 .
16800	 .
16900	 .
17000	DRAW A LINE FROM THE FUNCTION CALL  (IMPOSS FEATURE SCENE:FEATURES)
17100	          OF THE FUNCTION IMPOSS TO THIS NEW PIECE OF CODE, WHICH
17200	    IS ITS BODY:
17300	
17400	(IMPOSS
17500	  (LAMBDA (ARG1 ARG2)
17600	    (COMMENT IN ALL CALLS TO DATE, ARG1 IS INSTANTIATED AS FEATURE
17700	      AND ARG2 IS INSTANTIATED AS SCENE:FEATURES)
17800	    (COND
17900	      ((MEMBER ARG1 MUST:FEATURES)
18000		(COMMENT ARG1 OCCURS WITH PROBABILITY 1, SO IT HAD BETTER BE
18100	                         IN ARG2, THE RELEVANT PIECE OF THE WORLD)
18200		(NOT (MEMBER ARG1 ARG2))))
18300	      ((MEMBER ARG1 MUSTNOT:FEATURES)
18400		(COMMENT SINCE ARG1 SHOULD NEVER OCCUR, WE HAVE A 
18500	        	CONTRADICTION IF IT IS A MEMBER OF ARG2)
18600		(MEMBER ARG1 ARG2)))
18700	      (T (COMMENT WE MAY OR MAY NOT HAVE ARG1 IN ARG2; EITHER
18800			       CASE IS ALLOWABLE; SO WE
18900	                       NEVER HAVE A CONTRADICTION)
19000		NIL))))
19100	
19200	IMPOSS  has now been redefined as a BEING.
19300	
19400	(IN ALL CODE GENERATED,
19500	    ALL OCCURRENCES OF MODEL:FEATURES HAVE BEEN REPLACED
19600	    BY   (APPEND MUST:FEATURES MUSTNOT:FEATURES MAY:FEATURES))
19700	
19800	.FILL
19900	Notice that only a few messages have passed
20000	from user to PUP6 during all this processing.  The user has the  feeling
20100	of  merely  directing, constraining, and watching the activities of a
20200	busy programmer.   Unfortunately, "the user" is  not  generic;  there
20300	was  only one successful user. As was mentioned earlier, PUP6 insists
20400	on doing structured programming,  so  its  traces  are  superficially
20500	similar to  macro  expansion. Despite this concentration on planning,
20600	no BEINGs system 
20700	should mistakenly halt so long as any details remain.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY:  RESULTS)
00300	⊗27. REALITY:  RESULTS⊗*
00400		The  character of the dialogue (described in Section 6 and in
00500	Appendix 5) is, of course, one important measure of the  intelligence
00600	of  an  AP  system.   One which asked "What is the first instruction?
00700	What is the second...?" would be universal but worse than useless. In
00800	this  section  are  some  proposed  questions  one  should  ask  when
00900	confronted by a new AP system 
01000	which generates code heuristically from a dialogue.
01100	The answers pertaining to PUP6 are parenthesized after each question.
01200	Only capsules are given; fuller answers are located elsewhere.
01300		The questions break into two categories. First, one wants  to
01400	know  what the system does.  Most important, does it write a program?
01500	(yes.)
01600	If  so,  how  complex  is  that  task,  and  what  is   the   program
01700	specification  like? (a concept formation program, several pages long,
01800	from one specific protocol dialogue).  
01900	How precise must the user be:    may he err (no),
02000	forget (no), change his mind? (yes, in limited cases.) 
02100	How detailed must his  dialogue  be? (by construction, just about as
02200	detailed as if he were talking to a CS grad student programmer.) How
02300	closely  does  the  dialogue determine the details of the final code?
02400	(some inferences are made, and several representational choices, but
02500	much of the 
02600	final code is clearly determined by the precise user responses.)
02700	How does the user know where he is during the dialogue? (simulated cursors
02800	pointing to a graph representing synthesized code.)
02900		Quite  seriously, an important question is whether the system
03000	writes a second program. (yes.)  
03100	If so, how does it relate to the first  one
03200	synthesized? (both are inductive inference LISP programs.) 
03300	How much of the AP system is actually used in writing
03400	⊗4both⊗* programs? (49 BEINGs out of 79.) 
03500	One should ask what the full range of programs is
03600	which  the system has successfully synthesized. (the concept former, the
03700	grammatical inferrer, and the simple information manipulation system.)
03800	The dual questions to
03900	these inquire whether a program may be generated by several different
04000	dialogues (theoretically, but not practically),  
04100	and  what  the  range  of variability is. (theoretically large, but
04200	practically quite limited.) Similarly, what
04300	about the target language: is it a parameter? (no, always the same.) 
04400	How does it  relate  to
04500	the language the system is written in? (both written as BEINGs in 
04600	INTERLISP.)
04700		Does the system modify as well as write code? (yes, but not
04800	as its major mechanism.)   If so,  can
04900	it  modify  anybody's,  or only those programs it has written itself?
05000	(only its own, and only in simple ways.)
05100	What is its "style" of programming? (many supplementary comments,
05200	fairly clean structured programs only.) 
05300	One also wishes to know the  size
05400	of  the tool as well as the size of the job: How does the system size
05500	compare to target program size? (one order of magnitude larger.)
05600		Efficiency considerations are often the crucial
05700	pragmatic ones. Economics and current hardware restrict the amount of
05800	computation  which  may be done in toto; the expected lifetime of the
05900	universe restricts us from using the  most  elegant  algorithms;  and
06000	human  patience  restricts the interaction delay time (to a minute or
06100	two of real time). One must therefore  ask  things  like
06200	how  much  time  and  space  it  requires,  how long a delay there is
06300	between user inputs, etc. (one CPU hour, 100K, under a CPU minute 
06400	between responses.)
06500		The  second  class of questions concerns the theoretical side
06600	of the AP system.  What new ideas is it meant to experiment with? 
06700	(this is the subject of most of the preceding text; see esp. section 
06800	3.) How
06900	do each of these ideas fare? (many surprises; this is the subject of
07000	most of the remainder of this paper; see esp. section
07100	8.) Does it write its code in the right way?
07200	(it asks the right questions of  the  user  at  just  the  proper
07300	times with respect to the original protocol.)
07400	How extendable is it: how difficult is it to add new pieces
07500	of knowledge and to modify old ones? (theoretically easy, practically it
07600	requires familiarity with the system.)  Could  it  write  programs  in
07700	various fields (probably), in various styles (possibly), in various sizes?
07800	(the three target programs differ by less than one order of magnitude.)
07900		How is knowledge  represented  internally? (BEINGs, assertions,
08000	demons.)   Is  any  of  it
08100	duplicated? (not much above the LISP language level; some universal
08200	knowledge is factored out; e.g., how to CHOOSE-FROM a set of BEINGs.)
08300	If so, what and why? (some, by laziness; e.g.,
08400	how to bind variables.)  Why doesn't this system solve the AP
08500	problem? (it was mistakenly thought that the problems of dialogue were not
08600	central to "the AP problem.")
08700		Detailed answers  to most of the these questions are scattered
08800	throughout the earlier sections of this paper.  Below are its answers
08900	in detail to the remaining questions.  
09000		Let  us  briefly  describe  GI  and  INF, the second and
09100	third programs PUP6 synthesized.   GI  is  a  simple
09200	grammatical inference program. It builds up a set of plausible  rules,
09300	rather  than  enumerating  through  the space of all grammars. Yet it
09400	lacks most of the "tricks" of  the  best  g.i.  programs.   The  user
09500	repeatedly specifies a string, labelled LEGAL, ILLEGAL, or ??. In the
09600	latter case, GI must print out its guess and accept the correct label
09700	from  the  user.   In  all  three  cases,  it  must update its set of
09800	plausible rules to be at  least  consistent  with  all  positive  and
09900	negative  instances  observed. In some versions of GI the user coaxes
10000	PUP6 to generate, a parse tree may be maintained  and  inspected;  in
10100	other versions, just a list of the rules used during a parse is kept.
10200		INF is a data-retrieval-on-keys system.
10300	The user repeatedly types
10400	in a request to insert, delete, or inspect a  record  (e.g.,  INSERT:
10500	PASSENGER  Jones  FLIGHT  741  FROM SFO TO LAX CARRIER TWA LEAVE 7:15
10600	ARRIVE 8:00).  Any unspecified fields are treated  as  dont't  cares;
10700	thus the request is matched against entries in the data base.
10800		The table below shows how each type of knowledge was used  in
10900	writing the three target programs.  All numbers refer to BEINGs.
11000	
11100	.BEGIN
11200	.GROUP
11300	.NOFILL
11400	.FONT 7 "FIX20"
11500	.FONT 8 "NGB30"
11600	.SELECT 7
11700	.BREAK
11800	
11900	.ONCE CENTER
12000	        ⊗8U  S  E  D     I  N     S  Y  N  T  H  E  S  I  Z  I  N  G⊗*         
12100	
12200	TYPE OF          CF    CF    CF    CF     GI    INF     not     Crea    Crea    Crea    Total          
12300	KNOWLEDGE        GI    GI   INF   only   only   only    used    -ted    -ted    -ted    BEINGs
12400	                INF   only   only                       ever    in CF   in GI   in INF
12500	
12600	Programming      39     7     5     5     3      1       14       52      27      21      174
12700	Domain-Specific   0     3     0     9     8      1        5        4      10       3       43
12800	Total BEINGs     39    10     5    14    11      2       19       56      37      24      217
12900	.END
13000	
13100	The high percentage of programming BEINGs  which  were  used  in  all
13200	three  dialogues  is exciting.  The three domain-specific BEINGs used
13300	in both CF and GI  sessions  indicate  that  they  may  be  Inductive
13400	Inference  domain specific.  They aren't used in INF, which is not an
13500	inductive inference task. All three deal with partitioning a domain.
13600		A  specialization of a general programming BEING is listed as
13700	a programming BEING still  (in  the  CREATED  columns  of  the  above
13800	table.)  This  is  because  it remains sufficiently independent to be
13900	used in many ways, conceivably in many different programs.
14000		The  style  of  the synthesized programs is constrained since
14100	all code must be BEINGs. At a lower level,  there  are  many  trivial
14200	inefficiencies which are passed through a BEING which is to optimize
14300	LISP programs out of context, at a low level.  This BEING is
14400	vacuous now, but may soon contain a LISP optimizer being  written  by
14500	A.  Cohn of the SAIL AP group. Low level efficiency was intentionally
14600	ignored to expedite work  on  PUP6.   Nevertheless,  the  final  code
14700	produced  runs  in  about  the  same  time as the hand-coded versions
14800	(e.g., a few seconds per scene for CF).  It is several times as long,
14900	though,  since  it  must  be able to answer questions about what it's
15000	doing as it runs. The program produced by the system-player during
15100	the original protocol  lacked  this  ability,  of
15200	course.
15300		Although BEINGs can theoretically handle
15400	user errors, PUP6 was set up expecting that the user would never  err
15500	or  forget.  He could, after the program was finished, try it out and
15600	describe how he wished it changed. Occasionally, PUP6  actually  make
15700	the  right modifications. For example, INF,
15800	the simple data storage and retrieval on keys
15900	system which was written, was supposed to accept, access, and eliminate
16000	reservations.   After the synthesis is finished, the user tries
16100	out the program and finds that he is unable to delete more  than  one
16200	reservation  with  any  single  command. He complains about this, and
16300	PUP6 modifies the program so that he may specify a pattern,  and  all
16400	reservations  matching  that  pattern  will  be  purged.   While 
16500	assumptions of absolute 
16600	user reliability are reasonable for  little  programs,
16700	they  break  down  when the tasks reach the size of tens of pages and
16800	hours.
16900		One  crude  measure  of  concentration  of intelligence is to
17000	compare the system  and  target  code  lengths.  Ephemeral  numerical
17100	efficiency  data  such  as  this follows. PUP6 is 200 pages long when
17200	PRETTY-PRINTED, and has synthesized three programs, 7, 20, and 30
17300	pages long (1, 4, and 6 pages, when coded by hand.)
17400		A  brute  force  AP  system  would  require  a  time  roughly
17500	exponential  in  target  length, so log(time)/target_length (measured
17600	over several different programs and over several AP  systems)  is  an
17700	indicator  of  the  intelligence of an AP system.  For a good system,
17800	this number should (i) be small absolutely,  and,  more  importantly,
17900	(ii)  decrease  significantly as the target program length increases.
18000	For a ⊗4very⊗* good program writer, the  quantity  time/target_length
18100	stays   almost  constant.   This  is  not  quite  achieved  by  human
18200	programmers known to the author.
18300		Two important factors are omitted when simply comparing system
18400	and target lengths. First, one might improve any such measure by simply
18500	decreasing the size of a given system. This is wrong, since, e.g., 
18600	removing all the comments from a program shouldn't increase its
18700	intelligence!  Secondly, the total amount of distinct target programs
18800	should be considered. Compilers turn out programs small compared to
18900	themselves, but are valuable because of the vast variety of such programs
19000	they can put together.
19100	This factor reflects how much of the "guts" of the system can be used in
19200	writing many programs.
19300		PUP6  takes  60  cpu minutes to produce CF. During this time,
19400	300000 characters get typed out to the user, who  reponds  with  about
19500	4000  himself. The dialogue lengths are best specified in characters,
19600	since often the user will supply simply a number or  a  letter  or  a
19700	YES/NO  reply.   Dividing  these by a hundred, one can relate them to
19800	target and system lengths in lines. Even  the  character  counts  are
19900	very  rough,  because  the  format  of  the AP dialogue can easily be
20000	varied by a couple orders of magnitude.  The mean wait time  (between
20100	the user's input and the next machine output) is several seconds. The
20200	longest delay  between  successive  user  inputs  is  1  CPU  minute.
20300	Unfortunately,  PUP6  requires 100K to run in, which (with INTERLISP)
20400	exhausts the virtual memory of the current hardware being  used.  One
20500	would lose vast amounts of time by using intermediate storage devices
20600	or by running consecutive communicating jobs. Efficient use of multiple
20700	processors and of extended core storage might be made.
20800		INF  was  one fifth the size of CF, and took about a seventh
20900	as long to generate. The dialogue was shorter by a factor of three. The
21000	dialogue for the CF target program was too long and tiresome; the problem
21100	was even more acute for the INF program.
21200		Most  of  the  theoretical questions are answered by the very
21300	design of the system. Its ideational foundation has  been  discussed.
21400	When  the  user  sticks close to the original protocol, PUP6 asks the
21500	right questions at the right times because of its genesis  from  that
21600	annotated  protocol.   The  second  and third programs were attempted
21700	only to test its flexibility, and the results were mixed.
21800		First  the bright side. The increment to PUP6 to enable it to
21900	write the GI and the INF programs is encouragingly small. Almost  all
22000	the  programming-knowledge BEINGs are called in writing more than one
22100	of the programs. It is now clear  that  very  domain-specific  BEINGs
22200	were in control at the early, high levels. Later, more general BEINGs
22300	took over, followed by pure programming BEINGs.  The middle  category
22400	would  include inductive-inference-specific 
22500	BEINGs like PARTITION_A_DOMAIN.  
22600		Regrettably, incrementing the system with new domain-specific
22700	BEINGs is not feasable for the average user.  To add a BEING, he must
22800	specify  all  of  its relevant parts. Each is inputted either as LISP
22900	code, as an English sentence PUP6  is  capable  of  interpreting,  an
23000	English  sentence  PUP6  is  just  supposed  to  remember as a canned
23100	response, or by pointing to a part of an existing  BEING  and  saying
23200	"like  that  one,  except  ...", where the preceding ellipsis must be
23300	very simple.  The interactions between the BEINGs, and  the  existing
23400	set of BEINGs, need not be fully understood; but the set of allowable
23500	assertion templates, the mechanisms by which each part is  used,  the
23600	special  data types involved (VECTOR, TUPLE), and the precise actions
23700	of each new part ⊗4must⊗* be known in order to safely  inject  a  new
23800	BEING.
23900	This may be a result of the small amount of knowledge in PUP6. One would
24000	hope that a BEINGs system which was expert in a domain could assist the
24100	user in adding new domain-specific BEINGs, in the same way that the
24200	BEINGs which make up the target code are synthesized, through dialogue.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY:  CONCLUSIONS)
00300	⊗28. THEORY:  CONCLUSIONS⊗*
00400		The strengths and weaknesses of both BEINGs and PUP6 are
00500	reviewed.
00600	This experiment has helped clarify some 
00700	of the potential problems facing
00800	future AP work.
00900		While the number of  BEING-parts  is
01000	unimportant,  its magnitude (a few tens) may have significance to AP.
01100	The fact that is isn't ~1 may help explain the difficulty with predicate
01200	calculus representations; the fact that it isn't ~1000 
01300	may mean that the AP
01400	problem is tractible.
01500		Some of the ideas discussed at the  beginning  of  the  paper
01600	have proven themselves to be useful in getting PUP6 to work. 
01700	Little programs
01800	can indeed be treated as if their essence  is  nothing  more  than  a
01900	collection  of  answers.   The  gain  from  standardization  is 
02000	conceptually easy
02100	addition of pieces to the system; one "merely" adds new BEINGs to the
02200	community. Their interactions with all the existing BEINGs needn't be
02300	known in advance. As was discussed in the previous section, the 
02400	actual addition is beyond the power of the untrained user.
02500		Indications   are  that  one  ⊗4can⊗*  locate  relevant
02600	information by organizing the knowledge in a pool,  with  each  piece
02700	(i)  responsible  for  recognizing  when  it  is  relevant  and  (ii)
02800	indicating new relevant information indirectly  via  nondeterministic
02900	pattern-directed  retrievals  and  assertions.  Notice that this puts
03000	all control structure into the hands  of  the  BEINGs;  there  is  no
03100	central  monitor  in  PUP6.   A  BEING's answers may at various times
03200	indicate that it should be chosen to be in control, and it will  then
03300	take  over.   Notice  also  that this relevancy problem is central to
03400	program maintenance as well as synthesis. It is not clear whether 
03500	or not this really beats the exponential growth of this problem.
03600		The  fact  that target code is in the format of BEINGs limits
03700	the size of the target programs (≥ one page) and their efficiency  (a
03800	BEING-call  is a very slow and intricate process) and of course their
03900	style. The most startling result -- which should have been forseen --
04000	was that "intelligent" target code is synthesized. This was mentioned
04100	casually in the IDEAS section, 
04200	but its importance is clear: the target  code
04300	is  self-commenting  in the strong sense that the generated
04400	code can answer any
04500	(of our set of 29) questions about itself.  Those which make sense at
04600	compile-time  can  be  asked  then;  those  which  make  sense during
04700	execution may be asked then.  For example, CF begins  running.  After
04800	several  scenes have been processed, CF is waiting for a new one.  If
04900	the user interrupts  and  asks  what  it  is  doing,  CF  will  reply
05000	"awaiting user input of a brand new scene." One can ask why, how, who
05100	will be affected, and so on, interrupt as frequently  as  desired  --
05200	even  after  each  transfer of control from  one BEING to
05300	another. The actual questions and
05400	responses are not very impressive, but they are at least at the  same
05500	level as those which can be gotten from PUP6 itself as it runs.
05600		The set of questions the user was expected to want to ask the
05700	system  is  similar  to the questions one BEING wants to ask another.
05800	So when the "nice" user interrupts, his questions are almost always a
05900	simple  retrieval  from a property list (a GETP or a composition like
06000	EVALπ.GETP). When the average  user  interrupts,  his  questions  are
06100	often unintelligible to PUP6.
06200		Meaningful use of comments proved helpful. As an example, the
06300	comment at the end of the main outer loop was "COMMENT, INFINITE LOOP
06400	IN THIS PROG" (see page A5.10) for most of the session. Near the  end
06500	of  the  session,  the  CLARIFY_IMPROBABLE_SITUATION BEING recognizes
06600	this as a warning, works on introducing a breakaway  test,  and  then
06700	replaces  the  comment by one indicating that no infinite loop exists
06800	there anymore (see  page  A4.4).   The  advantage  to  embedding  our
06900	insertions in the code this way is that, at any stage, the user can
07000	inspect the code and get something meaningful  out  of  the  comments
07100	which are present.
07200		The  careful  bookkeeping   actually   did   eliminate   some
07300	carelessness  errors, though it had no effect on user errors or later
07400	program maintenance  directives.  These  latter  processes  are  less
07500	ill-defined  than  blind debugging, and in fact are about the same as
07600	programming itself [Dijkstra].  The deferral  of  decisions  has  the
07700	nice corollary of reducing (though not minimizing) communication with
07800	the slow user channel.
07900		Synthesizing a new, 
08000	clean target program  probably  would  require
08100	adding  a  few domain-independent BEINGs and several domain-specific
08200	BEINGs, and generalizing several parts of  several  existing  BEINGs.
08300	Since  the  dialogues  for  GI  and INF were not studied before-hand,
08400	their acceptability  would  have  demonstrated  the  success  of  the
08500	system.  Most of the existing BEINGs were used in generating these
08600	new programs, but a few new BEINGs had to be added. This addition
08700	process required detailed knowledge of the PUP6 system, not just of
08800	the domain.  Equally
08900	discouraging, the dialogue to write INF is too long and detailed
09000	for the task at hand.  It also  seems  that  the  front  end  is  too
09100	brittle  to  allow  anyone  unfamiliar with the system to easily work
09200	with it.
09300		The need for flexible communication stems  only
09400	partially from inter-user  differences.   A  serious  and  unexpected
09500	source  of  conflict  here  is the amount of inference the user wants
09600	done.  This level is relatively subjective, and may fluctuate rapidly
09700	even  with  one  user  writing one program. Perhaps there should be a
09800	dial he can set. At one extreme, the system would  ask  the  user  to
09900	verify  even  the  most  trivial  inductions.  At  the  other extreme
10000	setting, the system would probably write  the  target  program  after
10100	just a few brief user inputs. The user would then try out one program
10200	after another, interjecting just one or two comments each time, after
10300	which  the  system would come up with the next version.  This program
10400	modification mode seems appropriate for someone ignorant of LISP, who
10500	nevertheless has the I/O behavior of his target clearly in mind.
10600		Some of the BEING parts  proved  embarrassingly  unnecessary.
10700	The  CO-REQUISITES  part was never used.  The only activity which had
10800	to be done concurrently was demon activation. The AFFECTS part was of
10900	interest  to  the  user  occasionally,  but  never to any BEING.  The
11000	EFFECTS part originally had a twin, describing what would  happen  if
11100	each  BEING  were  ⊗4not⊗*  called right now.  In each case, this was
11200	merely a trivial restatement of the frame problem.  So,  like  STRIPS
11300	[Fikes],  PUP6  ignores  the  frame  problem:     all changes must be
11400	explicit.
11500		Much  of PUP6's comments are boring and unnecessary; this was
11600	felt to be an engineering problem which would be ignored in all but a
11700	"marketable"  AP system. This view was probably incorrect. One of the
11800	most severe AP problems is having  the  system  inform  the  user  of
11900	precisely  what  he should know -- no more nor less.  This requires a
12000	sophisticated  user  model  cleverly  interfaced   to   the   current
12100	programming task.
12200		Another problem with large, long dialogues is user  error.  A
12300	human  has  great  difficulty keeping "on top" of everything.  He may
12400	get lost, forget, change his  mind,  or  misunderstand.  Again,  this
12500	problem  was originally considered ignorable, but has shown itself to
12600	be  a  limiting  practical  factor  in  wide  accessability.  It  was
12700	necessary  to  create  a  forgetful-user  demon  to prevent anaphoric
12800	reference to something which, though uniquely determined, hadn't been
12900	mentioned within the past several seconds.
13000	Related to this is the problem of keeping
13100	the user informed of where he is. PUP6 simulated a continuous display
13200	of  the graph of the current partial program, augmented by static and
13300	dynamic cursors. This  simple 
13400	use  of  dynamic  and  textual  indices  seems
13500	insufficient.   The  user was still often confused, wishing a section
13600	referred to not by pointing but rather by a brief, meaningful (to him
13700	only!)  phrase.   This may also be one of the major AP problems which
13800	must be studied further.
13900		These  worries  about large dialogues arise because future AP
14000	systems are viewed as tools for writing programs which humans  simply
14100	cannot  manage  currently:      viable natural language systems, huge
14200	operating systems, better AP systems.
14300		One might argue against ever needing a
14400	system whose target programs will be longer and more complex than the
14500	system  itself.  First,  empirically, optimizing compilers are viable
14600	and yet they dwarf almost all the code they generate.  Second, as the
14700	complexity  of the transformation increases, the length of a compiler
14800	increases rapidly.  For a truly intelligent AP system, one  might  be
14900	willing  to  tolerate a program several times as large as anything it
15000	could produce.
15100		An  argument  exists  to  counter this one.  First, one might
15200	object to drawing  an  analogy  from  compilers;  many  entities  are
15300	capable  of  producing  things  more  sophistocated  than themselves,
15400	larger than themselves, etc. (consider evolution). Second,  it  seems
15500	that there is a manageable body of information which one needs master
15600	to do programming [informal].  Viewed differently, one can
15700	write  programs  as long as he wishes if the program is designed in a
15800	clean way. Thus the size of AP systems will probably
15900	level  off  (albeit  huge
16000	compared  to  existing  programs)  even as the size and complexity of
16100	their generated code continues to increase and,  eventually,  surpass
16200	them.  Finally,  we  must  consider why we want a good AP system:  to
16300	help  us  write  large  programs  easily,  programs  which  might  be
16400	unmanageable  today.   For  this  reason alone, our AP system must be
16500	able to deal with programs larger than itself.
16600		The whole design of BEINGs  is
16700	oriented   toward  this  large-scale  end.  One  cannot  write  tiny,
16800	super-efficient programs using BEINGs, any more  naturally  than  one
16900	can  generate  efficient machine code using a high level language. 
17000	A BEINGs system might simulate this activity, but it would be as
17100	awkward and opaque as if they were asked to simulate volleyball. By
17200	relinquishing  more  and  more  control  to  the  computer   language
17300	environment,  the  programmer  sacrifices specialization of the final
17400	code for ease of  constructing  it  and  for  its  greater  size  and
17500	complexity.
     

00100	.NEXT PAGE
00200	.EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE})
00300	⊗29. ACKNOWLEDGEMENTS⊗*
00400	
00500		There  are,  of  course,  countless  ideas  embodied  in  any
00600	concrete project.  Sweeping philosophical assumptions are made simply
00700	by deciding to do any type of programming [McCarthy], even moreso with
00800	Automatic Programming. Any
00900	Program-Understanding  Program  should  include the best parts of all
01000	the best old ideas.  PUP6 relies  on  concepts  gleaned  from  Actors
01100	[Hewitt],   Demons   [........],   heterarchy   [.....],   structured
01200	programming [Dijkstra], assertional  data  bases  and  flexible  data
01300	types  [Rulifson], pattern-directed invocation of procedural knowledge
01400	[........], the paradigm of AP by dialogue [Floyd], 
01500	and studies on  program
01600	specification techniques [Green].  Of course this list is incomplete;
01700	sophisticated ideas are captured in the languages themselves:   QLISP
01800	[Reboh],   INTERLISP   [Teitelman],  LISP  [McCarthy2],  and  English
01900	[Anonymous]. To this rich store, one may achieve new  heights  merely
02000	by synergy.
02100		Any success of the BEINGs project, as well as  the  precursor
02200	PUP  programs  [Green]  is due in large measure to the 
02300	creative energy of C.  Cordell  Green.   I  have
02400	also  drawn  upon  discussions  with
02500	D. Barstow, B.  McCune,  D.   Shaw,  E.
02600	Sacerdoti, L.
02700	Steinberg,  and  R.  Waldinger.   The generosity of SRI, in providing
02800	computer time and language consultations, should not go unmentioned.
02900	Also valuable were the critical readings of this paper by R. Davis
03000	and T. Winograd.